//
// Description: 5825. 最大兼容性评分和
// Created by Loading on 2021/7/25.
//

#include <bits/stdc++.h>

using namespace std;

/* 全排列 */
int maxCompatibilitySum(vector<vector<int>> &students, vector<vector<int>> &mentors) {
    int m = students.size();
    int n = students[0].size();
    /* 1 <= m, n <= 8 */
    /* 可以将二维数组转换成一位数组后进行全排列计算 */

    // 将一个 vector<int> 转换成一个 int 的方法
    auto vecToint = [](vector<int> &vec) {
        int res = 0;
        for (auto &x : vec) {
            res <<= 1;
            res |= x;
        }

        return res;
    };
    // 转换后的一维 vector<int>
    vector<int> st_per, men_per;
    for (int i = 0; i < m; ++i) {
        st_per.emplace_back(vecToint(students[i]));
        men_per.emplace_back(vecToint(mentors[i]));
    }

    int res = 0;
    /* 进行全排列之前需要先排序，才能找到所有的排列 */
    sort(st_per.begin(), st_per.end());
    do {
        int cnt = 0;
        // 计算兼容性评分和
        for (int i = 0; i < m; ++i) {
            int st = st_per[i], men = men_per[i];
            for (int j = 0; j < n; ++j) {
                if ((st & 1) == (men & 1)) {
                    ++cnt;
                }
                st >>= 1;
                men >>= 1;
            }
        }
        res = max(res, cnt);
    } while (next_permutation(st_per.begin(), st_per.end()));

    return res;
}

/* 回溯 */
int maxCompatibilitySum_DFS(vector<vector<int>> &students, vector<vector<int>> &mentors) {
    int m = students.size();
    int n = students[0].size();
    int res = 0;

    // 导师的访问标识数组
    vector<int> visit(m);

    // 回溯
    // index 表示当前学生下标
    function<void(int, int, vector<vector<int>> &, vector<vector<int>> &)> dfs = [&](int index, int sum,
                                                                                     vector<vector<int>> &students,
                                                                                     vector<vector<int>> &mentors) {
        // 一轮完成
        if (index == m) {
            res = max(res, sum);
            return;
        }

        // 给当前学生分配导师
        for (int i = 0; i < m; ++i) {
            // 当前导师未被访问
            if (visit[i] == 0) {
                // 计算当前轮次中一次匹配的兼容性评分和
                int cnt = 0;
                for (int j = 0; j < n; ++j) {
                    if (students[index][j] == mentors[i][j]) {
                        ++cnt;
                    }
                }
                // 标识置为 1
                visit[i] = 1;
                dfs(index + 1, sum + cnt, students, mentors);
                // 回溯完成，恢复标识
                visit[i] = 0;
            }
        }

    };

    dfs(0, 0, students, mentors);

    return res;
}

int main() {
    vector<vector<int>> students = {{0, 0, 1, 0, 0, 0, 0, 0},
                                    {1, 1, 0, 1, 0, 0, 0, 0},
                                    {1, 0, 0, 1, 1, 0, 0, 0},
                                    {1, 0, 1, 1, 1, 1, 1, 0},
                                    {1, 1, 0, 1, 1, 0, 1, 0},
                                    {0, 1, 0, 0, 0, 1, 1, 1},
                                    {1, 0, 0, 0, 1, 0, 0, 1},
                                    {1, 0, 0, 1, 1, 1, 0, 1}};
    vector<vector<int>> mentors = {{1, 1, 0, 0, 0, 1, 0, 0},
                                   {1, 1, 1, 1, 0, 1, 0, 0},
                                   {1, 0, 0, 1, 1, 0, 0, 1},
                                   {1, 1, 1, 0, 0, 0, 1, 0},
                                   {1, 0, 0, 0, 1, 0, 1, 1},
                                   {1, 0, 1, 1, 0, 1, 0, 0},
                                   {1, 1, 0, 1, 1, 0, 1, 0},
                                   {0, 1, 0, 0, 0, 1, 0, 0}};

    cout << maxCompatibilitySum(students, mentors) << endl;
    cout << maxCompatibilitySum_DFS(students, mentors) << endl;
}